In computer and telecommunications networks, devices such as routers and switches direct the flow of data packets between the data source and its destination. Where resources such as bandwidth of a particular router or switch is limited, known queuing techniques may be employed to prioritize the forwarding of data packets in accordance with discriminatory resource allocation criteria. In one such queuing technique, known as Class-based queuing (CBQ) and described in “Link Sharing and Resource Management Models for Packet Networks,” Sally Floys and Van Jacobson, IEEE/ACM Transactions on Networking, Vol. 3 No. 4, August, 1995, a hierarchical link-sharing mechanism is provided for use in packet-based networks where multiple entities, such as agencies, protocol families, or traffic types, share a single data link in a controlled fashion. In CBQ, traffic flows that share a single data link are bundled into logical queues, where each queue represents a class of flows. Resource allocation of the shared resource (e.g., bandwidth) is then performed for each class based on a set of rules that establish the share that each queue is to receive of the shared resource.
An example of a prior art CBQ link-sharing hierarchy may be seen in FIG. 1, where three agencies are connected to a single link. Each agency in turn provides various network services, such as FTP and TELNET, shown as branched flows, which in turn may comprise branched flows representing lower-level services, data flow groupings, or individual data flows. In CBQ, each node of the hierarchy shown in FIG. 1 receives a percentage share in the shared resource, with the shares equaling 100% for all nodes at the same level. Scheduling mechanisms are then used to ensure that each node receives its allotted resource allocation.
While CBQ addresses resource allocation for a single link-sharing hierarchy, CBQ does not address the use of multiple link-sharing hierarchies where each hierarchy models resource allocation according to a different set of criteria. For example, in FIG. 1, while a TELNET user in Agency A ought to receive a portion of the 10% of the available link resources allotted to all TELNET users in Agency A, the introduction of an additional link-sharing hierarchy as shown in FIG. 2 and which has different classes of users might indicate, for example, that the user is a VIP user who ought to receive a portion of the 80% of the available link resources allotted to all VIP-users. Unfortunately, current CBQ techniques do not offer a way to consider multiple link-sharing hierarchies and arrive at a single queuing solution.